#!/usr/bin/env python3


class Node:
    def __init__(self, left=None, data=None, right=None):
        self.left = left
        self.data = data
        self.right = right

    def postorder(self):
        if self.left is not None:
            self.left.postorder()
        if self.right is not None:
            self.right.postorder()

        print(self.data, end=' ')



def get_trees(inorder, preorder):
    trees = []
    root_value = preorder[0]
    if len(inorder) == 1:
        root = Node(data=root_value)
        return [root]
    index_in_inorder = inorder.index(root_value)
    left_tree_in_order = inorder[:index_in_inorder]
    right_tree_in_order = inorder[index_in_inorder + 1:]
    left_tree_size = len(left_tree_in_order)
    left_tree_pre_order = preorder[1: left_tree_size + 1]
    right_tree_pre_order = preorder[left_tree_size + 1:]
    if left_tree_size == 0:
        left_trees = [None]
    else:
        left_trees = get_trees(left_tree_in_order, left_tree_pre_order)
    if len(right_tree_in_order) == 0:
        right_trees = [None]
    else:
        right_trees = get_trees(right_tree_in_order, right_tree_pre_order)

    for left in left_trees:
        for right in right_trees:
            root = Node(left, root_value, right)
            trees.append(root)

    return trees


if __name__ == '__main__':
    inorder = [4, 2, 5, 1, 3, 6]
    preorder = [1, 2, 4, 5, 3, 6]
    trees = get_trees(inorder, preorder)
    print("可能的结果为: ")
    for tree in trees:
        tree.postorder()
        print()
